package java学习.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * @author 刘世锦
 * 2022-11-12 16:53:43	 当前时间
 */
//根据 逆波兰表示法，求表达式的值。 
//
// 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 
//
// 注意 两个整数之间的除法只保留整数部分。 
//
// 可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 
//
// 
//
// 示例 1： 
//
// 
//输入：tokens = ["2","1","+","3","*"]
//输出：9
//解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
// 
//
// 示例 2： 
//
// 
//输入：tokens = ["4","13","5","/","+"]
//输出：6
//解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
// 
//
// 示例 3： 
//
// 
//输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
//输出：22
//解释：该算式转化为常见的中缀算术表达式为：
//  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
//= ((10 * (6 / (12 * -11))) + 17) + 5
//= ((10 * (6 / -132)) + 17) + 5
//= ((10 * 0) + 17) + 5
//= (0 + 17) + 5
//= 17 + 5
//= 22 
//
// 
//
// 提示： 
//
// 
// 1 <= tokens.length <= 104 
// tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数 
// 
//
// 
//
// 逆波兰表达式： 
//
// 逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。 
//
// 
// 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。 
// 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。 
// 
//
// 逆波兰表达式主要有以下两个优点： 
//
// 
// 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 
// 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中 
// 
// Related Topics 栈 数组 数学 
// 👍 628 👎 0

public class 逆波兰表达式求值{
	public static void main(String[] args) {
		Solution solution = new 逆波兰表达式求值().new Solution();
		String[] tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
//		String[] tokens = {"4","13","5","/","+"};
		System.out.println(solution.evalRPN(tokens));

	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//                0    1   2    3  4
//输入：tokens = ["4","13","5","/","+"]
//输出：6
//解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

// 	使用栈： 符号不必进栈，将4个操作符分开计算，对对碰

	/**
	 * 用栈的特点：并没有将所有元素进栈，而是遍历到指定条件后去筛选
	 *
	 */
	public int evalRPN(String[] tokens) {
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < tokens.length; i++) {

			if (tokens[i].equals("+")){
				stack.push(stack.pop()+stack.pop());
			}else if(tokens[i].equals("-")){
				stack.push(-stack.pop()+stack.pop());

			} else if (tokens[i].equals("*")){
				stack.push(stack.pop()*stack.pop());

			}else if(tokens[i].equals("/")){
				int op2 = stack.pop();
				int op1 = stack.pop();
				stack.push(op1/op2);
			}else{
				stack.push(Integer.valueOf(tokens[i]));
			}
		}
		return stack.pop();
	}

		public int evalRPNfail(String[] tokens) {
		ArrayList<String> list = new ArrayList<>(Arrays.asList(tokens));
		if (tokens.length<3){
    		return 0;
		}
    	int op1 = 0; int op2 = 0,len = list.size();
		for (int i = 1; i < len; i++) {
			if (list.get(i).equals("+")){
				op1 = Integer.parseInt(list.get(i-2));
				op2 = Integer.parseInt(list.get(i-1));
				list.set(i-2, String.valueOf(op1+op2));
				list.remove(i-1);
				list.remove(i-1);

			}else if (list.get(i).equals("-")){
				op1 = Integer.parseInt(list.get(i-2));
				op2 = Integer.parseInt(list.get(i-1));
				list.set(i-2, String.valueOf(op1-op2));
				list.remove(i-1);
				list.remove(i-1);

			}else if (list.get(i).equals("*")){
				op1 = Integer.parseInt(list.get(i-2));
				op2 = Integer.parseInt(list.get(i-1));
				list.set(i-2, String.valueOf(op1*op2));
				list.remove(i-1);
				list.remove(i-1);

			}else if (list.get(i).equals("/")){
				op1 = Integer.parseInt(list.get(i-2));
				op2 = Integer.parseInt(list.get(i-1));
				list.set(i-2, String.valueOf(op1/op2));
				list.remove(i-1);
				list.remove(i-1);
			}
			len = list.size();
		}
		System.out.println(list);
		return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
